import java.util.ArrayList;

public class Board {
	
	int size;
	int board[][];
	final int BLANK = 0;
	int numPieces;
	int numBlack;	// black is 1
	int numWhite;	// white is -1
	
	int blackStable;
	int whiteStable;
	ArrayList<Integer> stable = new ArrayList<Integer>();
	
	Board(int aSize)
	{
			size = aSize;
			board = new int[size][size];
			board[size/2-1][size/2] = 1;
			board[size/2][size/2-1] = 1;
			board[size/2-1][size/2-1] = -1;
			board[size/2][size/2] = -1;
			numPieces = 4;
			numBlack = 2;
			numWhite = 2;
			blackStable = 0;
			whiteStable = 0;
		
	}
	
	void copy(Board b)
	{
		for(int i = 0; i < size; i++)
			for(int j = 0; j < size; j++)
				this.board[i][j] = b.board[i][j];
		this.numBlack = b.numBlack;
		this.numWhite = b.numWhite;
		this.numPieces = b.numPieces;
	}
	
	//checks if the value is in the list of stable pieces
	// x y player
	Boolean isInStableList(int x, int y, int player)
	{
		for(int i = 0; i<stable.size(); i+=3)
		{
			if(x==stable.get(i).intValue() && y == stable.get(i+1).intValue() &&
					player == stable.get(i+2).intValue())
				return true;
			
		}
		return false; 
	}
	
	
	Boolean isStable(int x,int y, int player)
	{	
		if(isInStableList(x,y, player) || !isOnBoard(x,y))
			return true;			
		
		return false;
	}
	
	
	//a piece that is stable is surrounded by 4 adjacent edges or stable pieces
	void possiblyAddToStable(int x, int y, int player)
	{
		if(x==0 && y == size-1)
		{
			stable.add(new Integer(x));
			stable.add(new Integer(y));
			stable.add(new Integer(player));
			if(player == 1)
				blackStable ++;
			else
				whiteStable ++;
			
			return;
		}	
		
		if(x==size-1 && y == 0)
		{
			stable.add(new Integer(x));
			stable.add(new Integer(y));
			stable.add(new Integer(player));
			if(player == 1)
				blackStable ++;
			else
				whiteStable ++;
			
			return;
		}
		
		if(x==size-1 && y == size-1)
		{
			stable.add(new Integer(x));
			stable.add(new Integer(y));
			stable.add(new Integer(player));
			if(player == 1)
				blackStable ++;
			else
				whiteStable ++;
			
			return;
		}
		
		if(x==0 && y == 0)
		{
			stable.add(new Integer(x));
			stable.add(new Integer(y));
			stable.add(new Integer(player));
			if(player == 1)
				blackStable ++;
			else
				whiteStable ++;
			
			return;
		}
		
		int stableAdjacent = 0;
		//check each direction a piece could be captured from
		if(isStable(x+1,y+1, player) || isStable(x-1,y-1,player))
		{
			stableAdjacent++;
		}
		
		if(isStable(x,y-1, player) || isStable(x,y+1,player))
		{
			stableAdjacent++;
		}
		
		if(isStable(x+1,y, player) || isStable(x-1,y,player))
		{
			stableAdjacent++;
		}
		
		if(isStable(x+1,y-1, player) || isStable(x-1,y+1,player))
		{
			stableAdjacent++;
		}
		
		if(stableAdjacent == 4)
		{
			stable.add(new Integer(x));
			stable.add(new Integer(y));
			stable.add(new Integer(player));
			if(player == 1)
				blackStable ++;
			else
				whiteStable ++;
			
			return;
		}
		
		
		
			
	}
	
	int someoneWon()
	{
		if(numBlack == 0)
			return -1;	//player two wins
		else if(numWhite == 0)
			return 1;	//player one wins
		
		if(noMoreValidMoves(-1) && noMoreValidMoves(1))
		{
			if(numBlack > numWhite)
				return 1;
			else if(numBlack < numWhite)
				return -1;
			else
				return 2;	// Draw
		}
		return 0;	// No winner yet
	}
	
	void flip(int x, int y)
	{
		board[x][y] = -board[x][y];
	}
	
	void flipAll(ArrayList<Integer> locationList)
	{
		for(int i =0; i<locationList.size(); i+=2)
		{
			flip(locationList.get(i).intValue(), locationList.get(i+1).intValue());
		}
	}
	
	
	boolean isOnBoard(int x, int y)
	{
		if(x<size && x>=0)
		{
			if(y<size && y>= 0)
			{
				return true;
			}
		}
		return false;
	}
	
	void insertPiece(int x, int y, int player)
	{
		int otherPlayer = -player;
		int offSetX, offSetY;
		ArrayList<Integer> toFlip = new ArrayList<Integer>();
		ArrayList<Integer> maybeFlip = new ArrayList<Integer>();
		//south east of xy
		if(isOnBoard(x+1,y+1))
		{
			offSetX = 1;
			offSetY = 1;
			if(board[x+offSetX][y+offSetY] == otherPlayer)
			{
				maybeFlip.add(new Integer(x+offSetX));
				maybeFlip.add(new Integer(y+offSetY));
				offSetX +=1;
				offSetY +=1;
				while(isOnBoard(x+offSetX, y+offSetY) && (board[x+offSetX][y+offSetY] == otherPlayer ||
						board[x+offSetX][y+offSetY] == player))
				{
					if(board[x+offSetX][y+offSetY] == player)
					{
						toFlip.addAll(maybeFlip);
						break;
					}
					else
					{
						maybeFlip.add(new Integer(x+offSetX));
						maybeFlip.add(new Integer(y+offSetY));
						offSetX +=1;
						offSetY +=1;
					}
				}
				
				
			}
			maybeFlip.clear();
		}
		
		//east of xy
		if(isOnBoard(x+1,y))
		{
			offSetX = 1;
			
			if(board[x+offSetX][y] == otherPlayer)
			{
				maybeFlip.add(new Integer(x+offSetX));
				maybeFlip.add(new Integer(y));
				offSetX +=1;				
				while(isOnBoard(x+offSetX, y) && (board[x+offSetX][y] == otherPlayer ||
						board[x+offSetX][y] == player))
				{
					if(board[x+offSetX][y] == player )
					{
						//System.out.println("size of toFlip: " + toFlip.size());
						//System.out.println("size of maybeFlip: " + maybeFlip.size());
						toFlip.addAll(maybeFlip);
						break;
					}
					else
					{
						maybeFlip.add(new Integer(x+offSetX));
						maybeFlip.add(new Integer(y));
						offSetX +=1;
					}
				}
				
				
			}
			maybeFlip.clear();
		}
		//north east of xy
		if(isOnBoard(x+1,y-1))
		{
			offSetX = 1;
			offSetY = -1;
			if(board[x+offSetX][y+offSetY] == otherPlayer)
			{
				maybeFlip.add(new Integer(x+offSetX));
				maybeFlip.add(new Integer(y+offSetY));
				offSetX +=1;
				offSetY -=1;
				while(isOnBoard(x+offSetX, y+offSetY) && (board[x+offSetX][y+offSetY] == otherPlayer ||
						board[x+offSetX][y+offSetY] == player))
				{
					if(board[x+offSetX][y+offSetY] == player)
					{
						toFlip.addAll(maybeFlip);
						break;
					}
					else
					{
						maybeFlip.add(new Integer(x+offSetX));
						maybeFlip.add(new Integer(y+offSetY));
						offSetX +=1;
						offSetY -=1;
					}
				}
				
				
			}
			maybeFlip.clear();
		}
		//north of xy
		if(isOnBoard(x,y-1))
		{
			offSetY = -1;
			if(board[x][y+offSetY] == otherPlayer)
			{
				maybeFlip.add(new Integer(x));
				maybeFlip.add(new Integer(y+offSetY));
				offSetY -=1;
				while(isOnBoard(x, y+offSetY) && (board[x][y+offSetY] == otherPlayer ||
						board[x][y+offSetY] == player))
				{
					if(board[x][y+offSetY] == player)
					{
						toFlip.addAll(maybeFlip);
						break;
					}
					else
					{
						maybeFlip.add(new Integer(x));
						maybeFlip.add(new Integer(y+offSetY));
						offSetY -=1;
					}
				}
				
				
			}
			maybeFlip.clear();
		}
		
		//north west of xy
		if(isOnBoard(x-1,y-1))
		{
			offSetX = -1;
			offSetY = -1;
			if(board[x+offSetX][y+offSetY] == otherPlayer)
			{
				maybeFlip.add(new Integer(x+offSetX));
				maybeFlip.add(new Integer(y+offSetY));
				offSetX -=1;
				offSetY -=1;
				while(isOnBoard(x+offSetX, y+offSetY) && (board[x+offSetX][y+offSetY] == otherPlayer ||
						board[x+offSetX][y+offSetY] == player))
				{
					if(board[x+offSetX][y+offSetY] == player)
					{
						toFlip.addAll(maybeFlip);
						break;
					}
					else
					{
						maybeFlip.add(new Integer(x+offSetX));
						maybeFlip.add(new Integer(y+offSetY));
						offSetX -=1;
						offSetY -=1;
					}
				}
				
				
			}
			maybeFlip.clear();
		}
		//south west of xy
		if(isOnBoard(x-1,y+1))
		{
			offSetX = -1;
			offSetY = 1;
			if(board[x+offSetX][y+offSetY] == otherPlayer)
			{
				maybeFlip.add(new Integer(x+offSetX));
				maybeFlip.add(new Integer(y+offSetY));
				offSetX -=1;
				offSetY +=1;
				while(isOnBoard(x+offSetX, y+offSetY) && (board[x+offSetX][y+offSetY] == otherPlayer ||
						board[x+offSetX][y+offSetY] == player))
				{
					if(board[x+offSetX][y+offSetY] == player)
					{
						toFlip.addAll(maybeFlip);
						break;
					}
					else
					{
						maybeFlip.add(new Integer(x+offSetX));
						maybeFlip.add(new Integer(y+offSetY));
						offSetX -=1;
						offSetY +=1;
					}
				}
				
				
			}
			maybeFlip.clear();
		}
		
		//south of xy
		if(isOnBoard(x,y+1))
		{

			offSetY = 1;
			if(board[x][y+offSetY] == otherPlayer)
			{
				maybeFlip.add(new Integer(x));
				maybeFlip.add(new Integer(y+offSetY));

				offSetY +=1;
				while(isOnBoard(x, y+offSetY) && (board[x][y+offSetY] == otherPlayer ||
						board[x][y+offSetY] == player))
				{
					if(board[x][y+offSetY] == player)
					{
						toFlip.addAll(maybeFlip);
						break;
					}
					else
					{
						maybeFlip.add(new Integer(x));
						maybeFlip.add(new Integer(y+offSetY));
						offSetY +=1;
					}
				}
				
				
			}
			maybeFlip.clear();
		}
		
		
		//west of xy
		if(isOnBoard(x-1,y))
		{
			offSetX = -1;
			if(board[x+offSetX][y] == otherPlayer)
			{
				maybeFlip.add(new Integer(x+offSetX));
				maybeFlip.add(new Integer(y));
				offSetX -=1;
				while(isOnBoard(x+offSetX, y) && (board[x+offSetX][y] == otherPlayer ||
						board[x+offSetX][y] == player))
				{
					if(board[x+offSetX][y] == player)
					{
						toFlip.addAll(maybeFlip);
						break;
					}
					else
					{
						maybeFlip.add(new Integer(x+offSetX));
						maybeFlip.add(new Integer(y));
						offSetX -=1;
					}
				}
				
				
			}
			maybeFlip.clear();
		}
		//add the piece
		board[x][y] = player;
		possiblyAddToStable(x,y,player);
		if(player == 1)
		{
			numBlack += toFlip.size()/2+1;
			numWhite -= toFlip.size()/2;
		}
		if(player == -1)
		{
			numBlack -= toFlip.size()/2;
			numWhite += toFlip.size()/2+1;
		}
		//flip all valid pieces
		flipAll(toFlip);
		numPieces++;

	}
	
	boolean isValidMove(int x, int y, int player)
	{
		if(board[x][y] != 0)
			return false;
		// check spot above
		if( y-1 >= 0 )
		{
			int tempy = y;
			if(board[x][--tempy] == -player)
			{
				if( tempy-1 >= 0 )
				{
					while(board[x][--tempy] != BLANK)
					{
						if(board[x][tempy] == player)
							return true;
						if( !(tempy-1 >= 0) )
							break;
					}
				}
			}
		}
		// check spot below
		if( y+1 < size )
		{
			int tempy = y;
			if(board[x][++tempy] == -player)
			{
				if( tempy+1 < size )
				{
					while(board[x][++tempy] != BLANK)
					{
						if(board[x][tempy] == player)
							return true;
						if( !(tempy+1 < size) )
							break;
					}
				}
			}
		}
		// check spot left
		if( x-1 >= 0 )
		{
			int tempx = x;
			if(board[--tempx][y] == -player)
			{
				if( tempx-1 >= 0 )
				{
					while(board[--tempx][y] != BLANK)
					{
						if(board[tempx][y] == player)
							return true;
						if( !(tempx-1 >= 0) )
							break;
					}
				}
			}
		}
		// check spot right
		if( x+1 < size )
		{//System.out.println("1piece: "+x+","+y+" = "+board[x][y]);
			int tempx = x;
			if(board[++tempx][y] == -player)
			{//System.out.println("2piece: "+x+","+y+" = "+board[x][y]);
				if( tempx+1 < size )
				{
					while(board[++tempx][y] != BLANK)
					{
						//System.out.println("3piece: "+x+","+y+" = "+board[x][y]);
						if(board[tempx][y] == player)
							return true;
						if( !(tempx+1 < size) )
							break;
					}
				}
			}
		}
		// check spot up-left
		if( y-1 >= 0 && x-1 >= 0)
		{
			int tempx = x;
			int tempy = y;
			if(board[--tempx][--tempy] == -player)
			{
				if( tempy-1 >= 0 && tempx-1 >= 0 )
				{
					while(board[--tempx][--tempy] != BLANK)
					{
						if(board[tempx][tempy] == player)
							return true;
						if( !(tempy-1 >= 0 && tempx-1 >= 0) )
							break;
					}
				}
			}
		}
		// check spot up-right
		if( y-1 >= 0 && x+1 < size)
		{
			int tempx = x;
			int tempy = y;
			if(board[++tempx][--tempy] == -player)
			{
				if( tempy-1 >= 0 && tempx+1 < size )
				{
					while(board[++tempx][--tempy] != BLANK)
					{
						if(board[tempx][tempy] == player)
							return true;
						if( !(tempy-1 >= 0 && tempx+1 < size) )
							break;
					}
				}
			}
		}
		// check spot bottom-left
		if( y+1 < size && x-1 >= 0 )
		{
			int tempx = x;
			int tempy = y;
			if(board[--tempx][++tempy] == -player)
			{
				if( tempy+1 < size && tempx-1 >= 0 )
				{
					while(board[--tempx][++tempy] != BLANK)
	 				{
						if(board[tempx][tempy] == player)
							return true;
						if( !(tempy+1 < size && tempx-1 >= 0) )
							break;
					}
				}
			}
		}
		// check spot above
		if( y+1 < size && x+1 < size )
		{
			int tempx = x;
			int tempy = y;
			if(board[++tempx][++tempy] == -player)
			{
				if( tempy+1 < size && tempx+1 < size )
				{
					while(board[++tempx][++tempy] != BLANK)
					{
						if(board[tempx][tempy] == player)
							return true;
						
						if( !(tempy+1 < size && tempx+1 < size) )
							break;
					}
				}
			}
		}
		
		return false;
		
	}
	
	boolean noMoreValidMoves(int player)
	{
		for(int i = 0; i < size; i++)
		{
			for(int j = 0; j < size; j++)
			{
				if(isValidMove(i, j, player))
					return false;
			}
		}
		return true;
	}
		
}
